1. Field of the Invention
The present invention is related to the field of congestion management for networks, and more specifically to a congestion control algorithm for allocating, among competing packetized data from different ports in a distributed control environment such as a channel bank, priority for transmission through a high bandwidth link. A typical such link is a time division multiplexing link, with its time division multiplexing scheme ignored for communicating packetized data.
2. Description of the Related Art
In the early 1970s, telephone service began using a time division multiplexed (TDM) communications system, known as D4, that used a channel bank to multiplex and communicate time division multiplexed (TDM) voice signals over a communications link, such as a T1 link. The channel bank typically carried 24 digital voice signals between central telephone offices using only one pair of wires in each direction instead of the normal 24 pairs of wires required to communicate the 24 voice signals in analog form. This capability was achieved by digitizing and time division multiplexing the 24 analog voice signals into 24 channels or timeslots. In the TDM system, each of the channels is allocated a predetermined, equal amount of time (corresponding to a predetermined bandwidth) within each frame of the T1 link to communicate any data. Each channel is always allocated its predetermined amount of time, even if that channel has no voice data to transmit. In addition to communicating voice signals, these systems can also communicate digital data because the D4 system was designed to handle digital data. The systems are still widely used today to carry voice traffic between central telephone offices. Therefore, the communications hardware and the network necessary for this D4 system are readily available.
A typical time division multiplexed (TDM) system, such as the D4 system, has a data rate of 1.544 million bit per second (Mbps) wherein timeslots of 64 Kbps are fixedly allocated to each channel unit. The 1.544 Mbps data rate is typically known as a T1 carrier.
FIG. 1 is a block diagram of a conventional time division multiplexed (TDM) communications system channel bank 20. The channel bank communicates a plurality of signals from a plurality of users over a communications link wherein each of the users has a specified timeslot assigned to it, in which it can communicate data over the communications link. The TDM system shown is a D4 channel bank, but the invention is not limited to a particular type of channel bank.
The D4 channel bank 20 can be used by a plurality of users 22 connected to a plurality of channel units 24-28, and the plurality of channel units can be known as a channel bank. In the D4 system shown, there are a maximum of twenty-four users and a maximum of twenty-four channel units so that there is a one-to-one correspondence between channel units and users. As described below in more detail, each channel unit has a fixed 8-bit timeslot assigned to it, in which that channel can communicate data. Each channel unit can communicate analog voice signals or digital data signals, as described below. For transmission, the data generated by any channel can be sampled eight thousand (8000) times per second so that eight thousand 8-bit samples (for a total of 64 Kbps data rate for each channel) can be generated for each channel, as described below in more detail.
The details of the D4 TDM communications system will now be described. For time division multiplexing in a D4 system, each of the twenty-four analog voice signals are low pass filtered and sampled at a rate of 8000 time per second by a voice card. Each of these analog samples are digitized to form 8-bit digital samples by a well-known analog-to-digital converter, and then these twenty-four 8-bit digital samples are concatenated together to form a 192-bit signal as shown in FIG. 2. These voice cards also communicate signaling information, such as ringing indication, idle indication or busy indication, required by the voice signals using two signaling bits known as A and B.
Returning to FIG. 1, the TDM D4 system can also send digital data using a data card to replace one or more of the voice cards. For digital data, there is no need to sample or digitize the digital data, and there are not any signaling information. Therefore, the D4 system has a TNEN bus for indicating to the transmit unit and the receive unit whether analog voice signals or digital data is being communicated. As described above, the common equipment acts as an interface between the transmit and receive unit and the T1 link.
During the transmission of data by a channel unit, the channel unit transmits the analog voice or digital data to a backplane bus 30, which in turn sends the data from all of the channel units to a transmit unit 32. The transmit unit converts the analog voice signals to digital signals, and then sends the digital signals (voice and data) to a common equipment 34. The common equipment transmits the digital data over a T1 link 36. As is well known, the T1 link can have a data transfer rate of 1.544 million bits per second (Mbps). In addition, the common equipment can control the channel units in order to fixedly allocate a data rate to each channel unit using a control bus.
In more detail, during transmission, the transmit unit gives each channel unit some addressing signals, TSP and TSQ that provide a unique address for each channel unit and indicates to each channel unit where in the T1 frame the timeslot for that channel unit is located. The transmit unit also gives each channel unit that communicates digital data a clock signal, TDCLK, and a serial data bus, TDATA. Each data channel unit transmits digital data over the TDATA bus only during its timeslot. The voice cards, also known as voice channel units, do not use the TDATA bus.
For the transmission of analog voice signals, a slightly different system is used, because, at the time that the D4 system was designed, analog to digital (A/D) and D/A converters were too expensive. A single high speed A/D converter was built into the transmit unit and a D/A converter into the receive unit to handle the conversion of analog voice signals. Therefore, there is a bus, called TPAM, between the voice channel units and the transmit unit that carries analog signals. Thus, during its assigned timeslot, a voice channel unit is enabled by a TWD signal to place an analog voltage onto the TPAM bus. The signaling information, as described above, for the voice signals are sent to the transmit unit over a TA and TB bus. The digital data channel units do not use the TPAM, TA or TB buses.
For receiving voice and digital data signals, the receive unit provides addressing leads, RSP and RSQ, to the channel units that provide a unique receive address to each channel unit, so that each channel unit can identify its timeslot of the T1 link. Each channel unit also receives a clock signal, RCLK. The digital channel units also receive the received digital data on a RNPCM bus, where the channel unit can latch onto the appropriate 8 bits of digital data during its timeslot. For analog signals, the signals are converted back into analog signals by the D/A converter in the receive unit, and then placed on an RPAM bus. Then a RWD signal from the receive unit indicates to each channel unit when to store the analog voltage on the RPAM bus. The signaling information is placed on a RSAB bus. To more fully understand the TDM system, the format of the TDM signal will be briefly described.
FIG. 2 is a schematic of a format of the signals generated by the channel bank shown in FIG. 1. A TDM signal 50 can be 193 bits long, derived from an 8-bit sample 52 for each of the twenty-four channel units and a framing bit 54. Each of the channels can be sampled eight thousand (8000) times per second, so that the total data rate for each channel is sixty-four thousand bits per second (64 Kbps), and the total data rate of all of the data and the framing bit is equal to the total data rate of the T1 link, which is 1.544 Mbps. However, if one or more of the channel units does not have any data to communicate, then the timeslot assigned to that channel unit will be unused, and thus, some bandwidth of the T1 link is wasted.
Because conventional channel banks, such as the D4 system, have allocated fixed time slots for each channel, these systems suffer from an inefficient use of bandwidth and cannot dynamically allocate that bandwidth. For example, if one or more channels do not have any voice or data signals to transmit at a particular time, the timeslot assigned to that channel unit in the T1 frame is unused. In addition, if a particular channel has a need for more bandwidth than the allocated time slot, the TDM system does not allow that channel to request or receive any extra bandwidth.
Due to such shortcomings, a number of alternative packet-based communications systems, such as asynchronous transfer mode (ATM), X.25 protocol, and frame relay, have been developed that do not assign fixed timeslots to each channel, but dynamically allocate bandwidth according to need. These packet-based communications systems are best used for digital data, because digital data tends to be communicated in bursts. For example, a user sending a computer file that is 100 Kbytes long will need to send the entire 100 Kbytes as quickly as possible, but then will not require any more bandwidth until another transmission.
These packetized communications systems permit the total bandwidth of the communications link to be allocated in any manner depending on the need of the channels. For example, a single channel can use the entire bandwidth for several seconds because that channel has high priority digital data, such as an e-mail message or a computer file, that must be transmitted immediately. Most of the packetized communications systems provide some system for preventing any particular channel from over-using the communications link. These packetized systems, however, cannot use the hardware of an existing time division multiplexed channel bank, such as D4. Therefore, these packet-based systems require specialized hardware.
Since bandwidth allocation in a TDM system is dedicated, there is no requirement for a bandwidth allocation mechanism to ensure fair delivery of bandwidth such as is required in packet-based systems. No established mechanism exists to ensure fair delivery of bandwidth for packet-based systems using TDM based hardware. Accordingly, a need exists to provide fair, low latency, delivery of packet-based bandwidth in a TDM system.
The present invention overcomes these problems and limitations of the prior art.
Generally, the present invention provides a mechanism for fair, low latency packet-based bandwidth delivery in a distributed control environment such as a channel bank system, additionally using a special priority scheme. The priority scheme allows priority depending on prior use to enforce fairness and other objectives.
According to the priority scheme, each user or port of the distributed control environment is assigned a priority number. Data delivery to the TDM system is regulated according to the priority number.
The priority scheme is for users who are guaranteed only a minimum traffic rate or Committed Information Rate (CIR). They are allowed to temporarily send a burst of traffic or a committed burst (Bc) for short intervals at a higher rate in packet-based delivery systems. The priority assigned to user traffic is based on an amount of bandwidth allocation unused by the User over a given amount of time, and a total traffic history.
The priority scheme uses a xe2x80x9cwater levelxe2x80x9d in a leaky bucket priority scheme to fairly assign priority within a high or low priority band.
A first water level in a first bucket is associated with an amount of allotted bandwidth unused by the channel unit. A second water level in a second bucket is associated with an amount of unused allotted bandwidth exceeding an overflow level of the first bucket. A third water level in a third bucket is associated with the total port bandwidth utilization history.
A high priority value is derived from the first water level, when the first water level is above zero. A medium priority value is derived from the second water level, when the first water level is zero, but the second is still above zero. A low priority value is derived from the third water level, when the water levels of both the first and second buckets are zero.
The first bucket is dimensioned as the configured committed burst capacity (Bc) for a given User connection. The water level in the first bucket represents the current bandwidth delivery rate for the User. If the water level is above zero, the User is sending traffic below their CIR. If the water level is zero, the User has sending traffic above their CIR. In another aspect of the invention, the total port bandwidth utilization history is preferably also accounted for, when the priority is assigned in the high band.
The second bucket represents bandwidth accumulated for the User in excess of the CIR and the committed burst bandwidth (Bc). Thus if a User does not use their CIR nor their committed burst bandwidth for enough time, the User will accumulate excess bandwidth credit (Be), up to a configured point.
Credits are subtracted from the first or second bucket for use of bandwidth, which lowers the respective water level. The subtraction is from the first bucket, if it can afford it, or otherwise from the second.
The third bucket is associated with the total port bandwidth utilization history. It is further preferred that the total port bandwidth utilization history is differentially aged, to favor recent history over older history, and optionally further compensated to favor long quiet times.
In all cases, the actual priority value is determined by a discrete mapping of the water level onto a range of high priority values in the high priority band. The water level is mapped also as a function of the total bucket capacity.
An advantage of the invention is that all users can receive the highest priority level for their traffic bandwidth allocation regardless of their preallocated bandwidth setting. It also means that all users will be throttled to the same percentage of their CIR when congestion occurs.
Since the packetized data is not assigned any particular time slot, the bandwidth that is otherwise wasted by TDM communication systems with fixed timeslots is reduced or eliminated.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment which proceeds with reference to the drawings.